Image data having a large data amount is not suitable for storage or transmission unless it undergoes processing. Generally, image data is compression-coded to decrease the data amount. A general image encoding apparatus will now be described.
A digital image captured by an image sensing device or the like is divided into tiles each having a desired rectangular size. Each tile is further divided into predetermined two-dimensional MBs (macroblocks) (FIG. 5). Each MB data undergoes orthogonal transform and is thus converted from color space data to transform coefficients in the frequency space.
Quantization processing is also performed for the transform coefficients as needed. If the data pattern of the image extends across a plurality of blocks, intra-frame prediction is performed to obtain the quantized transform coefficients in accordance with the frequency bands, thereby further decreasing the strength of the transform coefficients. However, if the quantized value changes depending on the coefficient position in a block or between blocks, correlation according to the frequency bands of the transform coefficients is not necessarily maintained even if the data pattern of the image extends across a plurality of blocks. It is therefore not always possible to suppress the strength of the transform coefficients by intra-frame prediction. In such a case, the intra-frame prediction processing may be omitted.
The two-dimensional transform coefficients which have undergone quantization and intra-frame prediction are sorted into one-dimensional data by continuously placing significant coefficients ahead and runs (zeros) behind. Thus sorted one-dimensional data is entropy-coded to generate a code stream.
The code stream generated in the above-described way is reconstructed into the image in accordance with a reverse processing procedure.
An image encoding apparatus which converts each of a number of blocks represented by JPEG, MPEG2, MPEG4, JPEG-XR, and the like uses run-length encoding for entropy encoding. Run-length encoding scans two-dimensionally arrayed transform coefficients in accordance with a predetermined pattern to sort them into a one-dimensional array, thereby encoding the length of continuous runs. FIG. 3A shows an example of the scan pattern. Scan is performed in the illustrated numerical order. This is called a “zigzag” pattern because the numerical order indicates a zigzag route. However, a predetermined pattern such as the “zigzag” pattern does not necessarily contributes to the encoding efficiency due to the following three reasons.
First, if conversion is performed across a plurality of blocks to suppress block distortion, the edge is enhanced, resulting in a larger transform coefficient variance and a higher transform coefficient strength. In this case, the strength of a low-frequency transform coefficient (the transform coefficient at the lower right corner of a block) does not always decrease. For this reason, the scan order for scanning transform coefficients from the upper left to the lower right of a block is not necessarily optimum.
Second, when the pixels in a block have a dependence in the vertical or horizontal direction, the frequency bands of transform coefficients tend to be localized in accordance with the dependence. In this case, a scan order which changes in the horizontal or vertical direction, as shown in FIG. 3B or 3C, is suitable.
Third, if a texture exists across blocks, transform coefficients are localized between the blocks in the same tendency. In this case, coefficient prediction is performed for the quantized transform coefficients, thereby suppressing the coefficient strength. The localization of the frequency bands of the transform coefficients changes depending on the prediction method. Hence, a scan pattern complying with the prediction method is necessary.
For the above-described reasons, it is preferable to select an optimum scan order suitable for an input image and an encoding scheme (e.g., Japanese Patent Laid-Open No. 2004-032788).
For an encoding scheme represented by JPEG-XR which further divides each MB into blocks so as to change the quantized values or intra-frame prediction method in each block, a method of changing the scan order for each block is suitable (e.g., Japanese Patent Laid-Open Nos. 2006-191628 and 07-050836).
For example, according to the scan order deciding method described in Japanese Patent Laid-Open No. 2006-191628, an MB including 16×16 pixels is divided into blocks each including 4×4 pixels, as shown in FIG. 4. Scan conversion of the blocks is performed in the order of A to P in FIG. 4. According to this method, the scan conversion result of the block A is analyzed, that is, the coefficients are analyzed in the order after sorting, thereby deciding the scan order of the next block B. Similarly, the scan conversion result of the block B is analyzed, that is, the coefficients are analyzed in the order after sorting, thereby deciding the scan order of the next block C. In the same way, depending on the scan conversion result of the current process target block, the scan order of the next block is decided. The scan order deciding method will be described in more detail with reference to FIG. 6.
First, in step S801, one transform coefficient C[n] (n≧0) is acquired in the one-dimensional order from a block that has undergone scan conversion. Next, in step S802, it is determined whether the coefficient C[n] acquired in step S801 is a run (zero). If the transform coefficient C[n] is a run, the process advances to determination in step S804. On the other hand, if the transform coefficient C[n] is a significant coefficient (nonzero), the process in step S803 is executed.
A statistical information table ScanTotals which counts the number of significant coefficients generated at each position of a 4×4 block is updated. For example, FIG. 7A shows an example of the statistical information table ScanTotals. FIG. 7A shows statistical information table values corresponding to the positions in the 4×4 pixel block corresponding to the scan order, as shown in FIG. 7B, for the descriptive convenience.
Note that the initial values of the statistical information ScanTotals are set as follows in some cases.{t*N,t*(N−1),t*(N−2), . . . ,t}
In general, a small integer (2 or 4) is selected as t. The value t may be decided by a quantization parameter used in quantization. Resetting the statistical information at a predetermined period allows the maximum bit length of the elements of the statistical information to be fixed.
There also exists a table ScanOrder representing the correspondence between the scan order and the positions of coefficients in a 4×4 pixel block. The initial order of the coefficient positions ScanOrder corresponding to the scan order is preferably decided causally between an image encoding processing apparatus and an image decoding processing apparatus. For example, when coefficient prediction has been done in the horizontal direction, the scan order is initialized to the order of preferentially scanning in the horizontal direction (FIG. 3C). On the other hand, when coefficient prediction has been performed in the vertical direction, the scan order is initialized to the order of preferentially scanning in the vertical direction (FIG. 3B). Note that the scan order in the horizontal direction may also be used as the initial scan order of a block which does not exhibit any specific directivity. Each of symbols a to o in FIG. 4 indicates the correspondence with a coefficient position in a given 4×4 pixel block shown in FIG. 4. Referring to FIG. 7B, the scan order table ScanOrder in the initialized status shown in FIG. 3B is represented by a to o in FIG. 4.
For a significant coefficient, the appearance frequency value of the corresponding element in the statistical information table ScanTotals is incremented (increased) in step S803.
In step S804, the ordering between two pieces of statistical information ScanTotals[n] and ScanTotals[n−1] is determined. ScanTotals[n]>ScanTotals[n−1] means that the number of times of significant coefficient generation is larger at the position of the transform coefficient C[n] than at the position of a transform coefficient C[n−1]. Hence, in step S805, conversion processing is performed for the coefficient position ScanOrder corresponding to the scan order and ScanTotals corresponding to it. If the statistical information ScanTotals[n] ScanTotals[n−1] in step S804, the scan order change processing is not executed.
The conversion processing in step S805 will be described in detail. In the conversion processing, to replace the coefficient positions ScanOrder[n] and ScanOrder[n−1] with each other, for example, the following calculations are performed.Temp=ScanOrder[n−1]ScanOrder[n−1]=ScanOrder[n]ScanOrder[n]=Temp
To replace the statistical information ScanTotals[n] and ScanTotals[n−1] with each other, for example, the following calculations are performed.Temp=ScanTotals[n−1]ScanTotals[n−1]=ScanTotals[n]ScanTotals[n]=Temp
Upon determining in step S806 that transform coefficient acquisition in the block for scan order decision has not ended yet, the process advances to step S807 to prepare for acquisition of the next coefficient. If all coefficients in the block have been acquired, the scan order decision procedure ends.
As described above, the coefficient position ScanOrder[n−1] corresponding to the scan order n−1 is causally decided using the statistical information ScanTotals[n] and ScanTotals[n−1] corresponding to the scan orders n and n−1. This allows to decide an optimum scan order stepwise. In addition, since the scan order can causally be decided, the encoding apparatus need not add, to the code stream, information to explicitly notify the decoding apparatus of the scan order.
As described above, in the scan order deciding method of deciding the scan order of a block based on the status of the preceding block, the scan order can change for each block. In such scan conversion processing, it is difficult to execute scan conversion of a plurality of blocks so the processing cannot sufficiently speed up.